{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random \n",
    "\n",
    "from eight_puzzle import Puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "puzzle = Puzzle()\n",
    "solution_lengths = list(np.arange(2,26,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "10\n",
      "12\n",
      "14\n",
      "16\n",
      "18\n",
      "20\n",
      "22\n",
      "24\n"
     ]
    }
   ],
   "source": [
    "# Generate a list of integers from 2 to 22 by 2\n",
    "solution_lengths = list(np.arange(2,24,2))\n",
    "\n",
    "# Create a dictionary to store the starting states\n",
    "# The format of the dictionary is number of actions in solution path: starting state\n",
    "starting_states = {}\n",
    "\n",
    "# Iterate through the wanted solution path lengths \n",
    "for solution_length in solution_lengths:\n",
    "    print(solution_length)\n",
    "    starting_states[solution_length] = []\n",
    "    \n",
    "    # Store 100 starting states for each solution length\n",
    "    while len(starting_states[solution_length]) < 100:\n",
    "        puzzle.set_goal_state()\n",
    "        states = [puzzle.goal_state]\n",
    "        while len(states) < solution_length + 1:\n",
    "            available_actions, _, _ = puzzle.get_available_actions(puzzle.state)\n",
    "            next_action = random.choice(available_actions)\n",
    "            new_state = puzzle.move(state = puzzle.state, action = next_action)\n",
    "            if new_state not in states:\n",
    "                states.append(new_state)\n",
    "                puzzle.state = new_state\n",
    "                \n",
    "        # Append the starting state to the dictionary\n",
    "        starting_states[solution_length].append(states[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "10\n",
      "12\n",
      "14\n",
      "16\n",
      "18\n",
      "20\n",
      "No Solution Found in first 10000 nodes generated\n",
      "No Solution Found in first 10000 nodes generated\n",
      "No Solution Found in first 10000 nodes generated\n",
      "No Solution Found in first 10000 nodes generated\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-91bc6c7d5167>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0mstarting_state\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mstarting_states\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0msolution_length\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m         \u001b[0mpuzzle\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstate\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mstarting_state\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m         \u001b[0mpuzzle\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0ma_star\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mheuristic\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m\"h1\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmax_nodes\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m10000\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mprint_solution\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mFalse\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      9\u001b[0m         \u001b[0mnodes_generated\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mpuzzle\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnum_nodes_generated\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0mh1_nodes_generated\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0msolution_length\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnodes_generated\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m/\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnodes_generated\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0;32mC:\\Users\\Will Koehrsen\\Documents\\EECS 391\\Programming\\eight_puzzle.py\u001b[0m in \u001b[0;36ma_star\u001b[0;34m(self, heuristic, max_nodes, print_solution)\u001b[0m\n\u001b[1;32m    289\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m    290\u001b[0m                 \u001b[1;31m# Check to see if new state has already been expanded\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m--> 291\u001b[0;31m                 \u001b[1;32mfor\u001b[0m \u001b[0mexpanded_node\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mexpanded_nodes\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    292\u001b[0m                     \u001b[1;32mif\u001b[0m \u001b[0mexpanded_node\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"state\"\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mnew_state\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m    293\u001b[0m                         \u001b[1;32mif\u001b[0m \u001b[0mexpanded_node\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"parent\"\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mnew_state_parent\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "h1_nodes_generated = {}\n",
    "max_nodes = 10000\n",
    "\n",
    "for solution_length in solution_lengths:\n",
    "    print(solution_length)\n",
    "    nodes_generated = []\n",
    "    for starting_state in starting_states[solution_length]:\n",
    "        puzzle.state = starting_state\n",
    "        puzzle.a_star(heuristic = \"h1\", max_nodes = 10000, print_solution=False)\n",
    "        if puzzle.num_nodes_generated != max_nodes:\n",
    "            nodes_generated.append(puzzle.num_nodes_generated)\n",
    "        else:\n",
    "            print(\"Maximum number of nodes reached with no solution!\")\n",
    "    h1_nodes_generated[solution_length] = sum(nodes_generated) / len(nodes_generated)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "10\n",
      "12\n",
      "14\n",
      "16\n",
      "18\n",
      "20\n",
      "22\n",
      "24\n",
      "No Solution Found in first 10000 nodes generated\n"
     ]
    }
   ],
   "source": [
    "h2_nodes_generated = {}\n",
    "max_nodes = 10000\n",
    "\n",
    "for solution_length in solution_lengths:\n",
    "    print(solution_length)\n",
    "    nodes_generated = []\n",
    "    for starting_state in starting_states[solution_length]:\n",
    "        puzzle.state = starting_state\n",
    "        puzzle.a_star(heuristic = \"h2\", max_nodes = max_nodes, print_solution=False)\n",
    "        if puzzle.num_nodes_generated != max_nodes:\n",
    "            nodes_generated.append(puzzle.num_nodes_generated)\n",
    "        else:\n",
    "            print(\"Maximum number of nodes reached with no solution!\")\n",
    "    h2_nodes_generated[solution_length] = sum(nodes_generated) / len(nodes_generated)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 7.06,\n",
       " 4: 12.54,\n",
       " 6: 19.79,\n",
       " 8: 29.15,\n",
       " 10: 46.36,\n",
       " 12: 81.17,\n",
       " 14: 145.38,\n",
       " 16: 277.26,\n",
       " 18: 436.43,\n",
       " 20: 688.66,\n",
       " 22: 1072.8,\n",
       " 24: 1544.34}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h1_nodes_generated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
